import com.sun.org.apache.xerces.internal.util.SAXLocatorWrapper;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lishuo
 * Date: 2023-12-17
 * Time: 19:50
 */
public class TestLinkedList {
    private static class ListNode {
        int val;
        ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }

    /**
     * 一切从反转链表开始
     * @param head
     * @return
     */
    public ListNode ReverseList (ListNode head) {
        // 方法一：前后指针反转法
        // 方法二：头插法
        ListNode res = new ListNode(-1);
        res.next = head;
        // 初始化前驱和当前结点
        ListNode pre = res;
        ListNode cur = head;
        // 反转链表（头插法）
        while (cur.next != null) {
            // 定义curNext指针
            ListNode curNext = cur.next;
            // 修改cur执行tmpNext
            cur.next = curNext.next;
            // 修改curNext指针指向
            curNext.next = pre.next;
            // 修改pre.next指向
            pre.next = curNext;
        }
        return pre.next;
    }

    /**
     * 反转部分链表
     * 注意：这里的反转使用头插法更为合适
     * @param head
     * @param m
     * @param n
     * @return
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // 加个表头
        ListNode res = new ListNode(-1);
        res.next = head;
        // 定义前序结点和当前结点
        ListNode pre = res;
        ListNode cur = head;
        // 找到m
        for (int i = 1; i < m; i++) {
            pre = cur;
            cur = cur.next;
        }
        // 此时反转部分链表涉及到三次指针改变
        // 每反转一个结点 pre.next 需要改变一次
        // 每反转一个节点 cur.next 和 cur.next.next 分别需要改变一次
        for (int i = m; i < n; i++) {
            ListNode tmp = cur.next;
            cur.next = tmp.next;
            tmp.next = pre.next;
            pre.next = tmp;
        }

        return res.next;
    }

    /**
     * 链表中的节点每k个一组翻转
     * 两种方法：非递归
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseKGroup1 (ListNode head, int k) {
        ListNode pre = new ListNode(-1);
        ListNode res = pre;
        ListNode cur = head;
        pre.next = head;
        while (cur != null) {
            ListNode tail = cur;
            for (int i = 1; i < k; i ++) {
                if (tail == null) {
                    break;
                }
                tail = tail.next;
            }
            if (tail == null) {
                break;
            }
            for (int i = 1; i < k; i ++) {
                // 头插反转
                ListNode curNext = cur.next;
                cur.next = curNext.next;
                curNext.next = pre.next;
                pre.next = curNext;
            }
            pre = cur;
            cur = cur.next;
        }
        return res.next;
    }

    /**
     * 链表中的节点每k个一组翻转
     * 两种方法：递归
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseKGroup2(ListNode head, int k) {
        // 判断遍历k次是否到达末尾
        ListNode tail = head;
        for (int i = 0; i < k; i ++) {
            // 如果不满足条件直接返回链表，无需翻转
            if (tail == null) {
                return head;
            }
            tail = tail.next;
        }

        // 如果遍历k次没有到达末尾则对这k个结点进行反转
        ListNode pre = head;
        ListNode cur = head.next;
        // 前后指针反转
        while (cur != tail) {
            ListNode curNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = curNext;
        }
        // 现在头结点指向尾巴
        head.next = reverseKGroup2(tail,k);
        // 返回反转后的头结点
        return pre;
    }

    /**
     * 合并有序链表，加个哨兵结点，迎刃而解
     * @param pHead1
     * @param pHead2
     * @return
     */
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // write code here
        // 解题思路：快慢指针
        if (pHead1 == null) {
            return pHead2;
        }
        if (pHead2 == null) {
            return pHead1;
        }
        // 增加一个头结点
        ListNode head = new ListNode(-1);
        ListNode cur = head;

        while (pHead1 != null && pHead2 != null) {
            if (pHead1.val < pHead2.val) {
                cur.next = pHead1;
                pHead1 = pHead1.next;
            } else {
                cur.next = pHead2;
                pHead2 = pHead2.next;
            }
            cur = cur.next;
        }
        // 将剩余的加上
        if (pHead1 == null) {
            cur.next = pHead2;
        } else {
            cur.next = pHead1;
        }
        return head.next;
    }

    /**
     * 这一题看似使用链表，实则考察堆
     * @param lists
     * @return
     */
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        // 根据每个子ListNode的首元素建立小堆
        Queue<ListNode> minHeap = new PriorityQueue<>((v1,v2)->{return v1.val - v2.val;});
        for (ListNode listNode: lists) {
            // 保证每个ListNode中至少有一个元素
            if (listNode != null) {
                minHeap.offer(listNode);
            }
        }
        // 建立一个哨兵头结点
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        // 遍历小跟堆，直到为空
        while (!minHeap.isEmpty()) {
            // 取出队首元素.进行连接
            ListNode poll = minHeap.poll();
            cur.next = poll;
            cur = cur.next;
            // 如果元素个数大于一，取出以后，继续假如队列
            if (poll.next != null) {
                poll = poll.next;
                minHeap.offer(poll);
            }
        }
        return head.next;
    }


    /**
     * 判断是否有环
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        // 思路：快慢指针，慢指针一次一步，快指针一次两步，有环最终一定能相遇
        if (head == null) {
            return false;
        }

        // 定义快慢指针
        ListNode fast = head;
        ListNode slow = head;
        // 遍历
        // 那个指针先走到末尾，判断哪个
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            // 快慢指针相遇表示有环
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    /**
     * 找环的入口结点（使用set）
     * @param pHead
     * @return
     */
    public ListNode EntryNodeOfLoop1(ListNode pHead) {
        // 方法一：要么使用set不重复的特性
        Set<ListNode> set = new HashSet<>();
        while (pHead != null) {
            if (set.contains(pHead)) {
                return pHead;
            }
            set.add(pHead);
            pHead = pHead.next;
        }
        return null;
    }

    /**
     * 找环的入口结点(固定套路)
     * @param pHead
     * @return
     */
    public ListNode EntryNodeOfLoop2(ListNode pHead) {
        // 方法二：要么固定套路：想让两个指针相遇，
        // 然后让fast指针从头部开始，二者同时向后遍历，
        // 最终的相遇点就是入口结点。
        ListNode fast = pHead;
        ListNode slow = pHead;
        // 找到相遇点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                break;
            }
        }
        // 判断是否相遇
        if (fast == null || fast.next == null) {
            return null;
        }
        // 更新fast，并同时遍历
        fast = pHead;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

    /**
     * 倒数第k个结点（使用一个列表）
     * @param pHead
     * @param k
     * @return
     */
    public ListNode FindKthToTail1 (ListNode pHead, int k) {
        // write code here
        // 方案一：搞一个列表
        List<ListNode> lists = new ArrayList<>();
        while (pHead != null) {
            lists.add(pHead);
            pHead = pHead.next;
        }
        // 找到下标
        int index = lists.size() - k;
        if (index < 0 || index == lists.size()) {
            return null;
        }

        return lists.get(index);
    }

    /**
     * 倒数第k个结点（快慢指针）
     * @param pHead
     * @param k
     * @return
     */
    public ListNode FindKthToTail2 (ListNode pHead, int k) {
        // write code here
        // 方案二：快慢指针
        if (pHead == null) {
            return null;
        }

        ListNode fast = pHead;
        ListNode slow = pHead;
        // 快指针先走k步，然后快慢指针同时走，快指针到达末尾，慢指针执行倒数第k个结点
        for (int i = 0; i < k; i ++) {
            // fast在k步之内走到末尾，说明没有倒数第k个结点
            if (fast == null) {
                return null;
            }
            // 注意这里的判断很讲究，一定是在快指针走之前判断，否则可能误判
            fast = fast.next;

        }
        // 快慢指针同步
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    /**
     * 删除倒数第k个结点（添加一个哨兵结点）
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        // 创建一个哨兵结点
        ListNode res = new ListNode(-1);
        res.next = head;

        // 定义结点
        ListNode pre = res;
        ListNode fast = head;
        ListNode slow = head;

        // 快指针先走n步
        for (int i = 0; i < n; i ++) {
            // 因为一定存在，这里就不必判断了
            fast = fast.next;
        }

        // 找到倒数第n个，和倒数第n个的pre
        while (fast != null) {
            pre = pre.next;
            fast = fast.next;
            slow = slow.next;
        }

        // 删除结点
        pre.next = slow.next;
        slow.next = null;

        return res.next;
    }

    /**
     * 两个链表的第一个公共结点（利用两个链表之和"相等"的特性）
     * @param pHead1
     * @param pHead2
     * @return
     */
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode head1 = pHead1;
        ListNode head2 = pHead2;

        // 利用相交链表加和长度相等特性
        // 即使没有交点，最终等于null时循环也会结束
        while (head1 != head2) {
            head1 = (head1 == null)? pHead2:head1.next;
            head2 = (head2 == null)? pHead1:head2.next;
        }
        return head1;
    }


    /**
     * 链表相加（时刻注意变量变动[写的时候head1和h1混淆了]）
     * 使用指针进行反转链表时，要么定义变量时让pre为null，要么最后将原来的“head”的next置为null
     * @param head
     * @return
     */
    public ListNode reverse(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while(cur != null){
            //断开链表，要记录后续一个
            ListNode temp = cur.next;
            //当前的next指向前一个
            cur.next = pre;
            //前一个更新为当前
            pre = cur;
            //当前更新为刚刚记录的后一个
            cur = temp;
        }
        return pre;
    }

    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }

        // 这种单向链表相加，首先需要进行反转
        // 首先反转两个链表（为了保证从低位开始相加）
        ListNode h1 = reverse(head1);
        ListNode h2 = reverse(head2);

        // 开始相加
        // 创建一个结果链表
        ListNode res = new ListNode(-1);
        // 记录进位
        int carry = 0;
        while (h1 != null || h2 != null || carry != 0) {
            int val1 = h1 == null ? 0 : h1.val;
            int val2 = h2 == null ? 0 : h2.val;
            System.out.println("111");

            int num = (val1 + val2 + carry)%10;
            carry = (val1 + val2 + carry)/10;
            // 构建结果链表(头插，无需最后再进行结果链表的反转)
            ListNode numNode = new ListNode(num);
            ListNode resNext = res.next;
            res.next = numNode;
            numNode.next = resNext;

            if (h1 != null) {
                h1 = h1.next;
            }
            if (h2 != null) {
                h2 = h2.next;
            }
        }
        return res.next;
    }

    /**
     * 链表排序（很简单，用额外的空间排序即可）
     * @param head
     * @return
     */
    public ListNode sortInList (ListNode head) {
        ArrayList<Integer> nums = new ArrayList();
        ListNode p = head;
        //遍历链表，将节点值加入数组
        while(p != null){
            nums.add(p.val);
            p = p.next;
        }
        p = head;
        //对数组元素排序
        Collections.sort(nums);
        //遍历数组
        for(int i = 0; i < nums.size(); i++){
            //将数组元素依次加入链表
            p.val = nums.get(i);
            p = p.next;
        }
        return head;
    }

    /**
     * 判断链表是否回文（直接反转即可）
     * @param head
     * @return
     */
    public ListNode reverse2(ListNode head) {
        // 使用双指针反转
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
    public boolean isPail (ListNode head) {
        // write code here
        if (head == null) {
            return true;
        }
        // 找中点
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // slow指向中点
        slow = reverse2(slow);
        fast = head;

        // 这里条件一定是slow为null
        while (slow != null) {
            if (slow.val != fast.val) {
                return false;
            }
            slow = slow.next;
            fast = fast.next;
        }
        return true;
    }

    /**
     * 链表奇偶重排（注意重连后，结点向后走）
     * @param head
     * @return
     */
    public ListNode oddEvenList (ListNode head) {
        if (head == null) {
            return null;
        }
        // write code here
        // 记录奇数头结点；记录偶数头结点
        ListNode odd = head;
        ListNode even = head.next;

        // 记录结果头结点
        ListNode evenHead = even;
        ListNode res = odd;

        // 开始连接（even走的快，避免空指针，条件这样写）
        while (even != null && even.next != null) {
            // 连接奇偶结点
            odd.next = odd.next.next;
            even.next = even.next.next;

            odd = odd.next;
            even = even.next;
        }

        // 最后连接一奇偶链表
        odd.next = evenHead;

        return head;
    }

    /**
     * 删除有序链表中的重复元素（注意双while循环需要考虑双重条件）
     * @param head
     * @return
     */
    public ListNode deleteDuplicates1 (ListNode head) {
        // write code here
        if (head == null) {
            return null;
        }
        // 思路：双指针遍历连接
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null) {
            // 找到一个不等于slow.val的元素
            while (fast != null && fast.val == slow.val) {
                fast = fast.next;
            }
            slow.next = fast;
            slow = fast;
        }

        return head;
    }

    /**
     * 删除链表中的重复元素,只保留出现一次的元素
     * @param head
     * @return
     */
    public ListNode deleteDuplicates2 (ListNode head) {
        // write code here
        if (head == null) {
            return null;
        }
        // 同样使用双指针
        ListNode slow = head;
        ListNode fast = head;
        // 记录结果头结点
        ListNode res = new ListNode(-1);
        ListNode resHead = res;
        while (fast != null) {
            // 记录不等元素距离。len = 1表示不重复
            int len = 0;
            // 找到第一个不等于slow.val的元素
            while (fast != null && fast.val == slow.val) {
                len ++;
                fast = fast.next;
            }
            if (len == 1) {
                // 此时slow指向即为不重复元素

                // 构造结果链表
                res.next = slow;
                res = res.next;
            }
            slow = fast;
        }
        // 不要忘记最后将res尾元素置空
        res.next = null;
        return resHead.next;
    }

    // 面试题 02.04. 分割链表(感觉不难)
    public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return null;
        }
        // 简单的方法：弄两个链表
        ListNode minHead = null;
        ListNode minPre = null;
        ListNode maxHead = null;
        ListNode maxPre = null;
        while (head != null) {
            if (head.val < x) {
                if (minPre == null) {
                    minHead = head;
                    minPre = head;
                } else {
                    minPre.next = head;
                    minPre = head;
                }
            } else {
                if (maxPre == null) {
                    maxHead = head;
                    maxPre = head;
                } else {
                    maxPre.next = head;
                    maxPre = head;
                }
            }
            head = head.next;
        }
        if (minHead == null) {
            return maxHead;
        }
        // 结果拼接(一个判断引发的血案)
        minPre.next = maxHead;
        if (maxHead != null) {
            maxPre.next = null;
        }
        return minHead;
    }




    public static void main(String[] args) {
        System.out.println("链表ToP101完成!");
    }
}
